package likou;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/09/20 08:45
 */
public class _673 {
    public static void main(String[] args) {
        _673 n = new _673();
        System.out.println(n.findNumberOfLIS(new int[]{1, 2, 4, 3, 5, 4, 7, 2}));
    }

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 1, res = 0;
        int[][] dp = new int[n][2];
        for (int[] d : dp) {
            Arrays.fill(d, 1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    if (dp[i][0] + 1 == dp[j][0]) {
                        dp[j][1] += dp[i][1];//个数+1
                    } else if (dp[i][0] + 1 > dp[j][0]) {
                        dp[j][0] = dp[i][0] + 1;//阶数
                        dp[j][1] = dp[i][1];
                        maxLen = Math.max(dp[j][0], maxLen);
                    }
                }
            }
            System.out.print(nums[i] + ": ");
            for (int[] d : dp) {
                System.out.print(Arrays.toString(d));
            }
            System.out.println();
        }
        for (int i = 0; i < n; i++) {
            if (dp[i][0] == maxLen) res += dp[i][1];
        }
        return res;
    }
}
